package org.example;

import java.util.LinkedList;
import java.util.List;

// 【Trie/字典树/前缀树原理及可视化】
// https://labuladong.online/algo/data-structure-basic/trie-map-basic/
public class TrieTree {
    // Trie 树就是 多叉树结构 的延伸，是一种针对字符串进行特殊优化的数据结构。
    // Trie 树在处理字符串相关操作时有诸多优势，比如节省公共字符串前缀的内存空间、方便处理前缀操作、支持通配符匹配等。

    // 本文仅是 Trie 树（也叫做字典树、前缀树）的原理介绍
    /*
    本站将会带你实现一个 TrieMap 和 TrieSet，先来梳理一下我们已经实现过的 Map/Set 类型：
    标准的
    哈希表 HashMap，底层借助一个哈希函数把键值对存在 table 数组中，有两种解决哈希冲突的方法。它的特点是快，即基本的增删查改操作时间复杂度都是 O(1)。
    哈希集合 HashSet 是 HashMap 的简单封装。

    哈希链表 LinkedHashMap，是
    双链表结构 对标准哈希表的加强。它继承了哈希表的操作复杂度，并且可以让哈希表中的所有键保持「插入顺序」。LinkedHashSet 是 LinkedHashMap 的简单封装。

    哈希数组 ArrayHashMap，是
    数组结构 对标准哈希表的加强。它继承了哈希表的操作复杂度，并且提供了一个额外的 randomKey 函数，可以在 O(1) 的时间返回一个随机键。ArrayHashSet 是 ArrayHashMap 的简单封装。

    TreeMap 映射，底层是一棵二叉搜索树（编程语言标准库一般使用经过改良的自平衡
    红黑树），基本增删查改操作复杂度是 O(logN)，它的特点是可以动态维护键值对的大小关系，有很多额外的 API 操作键值对。TreeSet 集合是 TreeMap 映射的简单封装。

    TrieSet 也是 TrieMap 的简单封装，所以下面我们聚焦 TrieMap 的实现原理即可。*/

    // 【Trie 树的主要应用场景】
    // Trie数是一种针对字符串有特殊优化的数据结构，这也许它又被叫做字典树的原因。Trie数针对字符串的处理有若干优势，下面一一列举。
    // 优势一：节省存储空间
//    public void saveSpace() {
//        // 回想哈希表的实现原理，键值对会被存到 table 数组中，也就是说它真的创建 "apple"、"app"、"appl" 这三个字符串，占用了 12 个字符的内存空间。
//        // 但是注意，这三个字符串拥有共同的前缀，"app" 这个前缀被重复存储了三次，"l" 也被重复存储了两次。
//        Map<String, Integer> map = new HashMap<>();
//        map.put("apple", 1);
//        map.put("app", 2);
//        map.put("appl", 3);
//
//        // 如果换成TrieMap来存储
//        // Trie树的键类型固定为String类型，值类型可以是泛型
//        TrieMap<Integer> trieMap = new TrieMap();
//        trieMap.put("apple", 1);
//        map.put("app", 2);
//        map.put("appl", 3);
//        // Trie 树底层并不会重复存储公共前缀，所以只需要 "apple" 这 5 个字符的内存空间来存储键。
//        // 这个例子数据量很小，你感觉重复存储几次没啥大不了，
//        // 但如果键非常多、非常长，且存在大量公共前缀（现实中确实经常有这种情况，比如证件号），那么 Trie 树就能节约大量的内存空间。
//    }
//
//    // 优势二：方便处理前缀操作
//    public void easyToHandle() {
//        TrieMap<Integer> map = new TrieMap<>();
//        map.put("that", 1);
//        map.put("the", 2);
//        map.put("them", 3);
//        map.put("apple", 4);
//
//        // "the" 是 "themxyz" 的最短前缀
//        System.out.println(map.shortestPrefixOf("themxyz")); // "the"
//
//        // "them" 是 "themxyz" 的最长前缀
//        System.out.println(map.longestPrefixOf("themxyz")); // "them"
//
//        // "tha" 是 "that" 的前缀
//        System.out.println(map.hasKeyWithPrefix("tha")); // true
//
//        // 没有以 "thz" 为前缀的键
//        System.out.println(map.hasKeyWithPrefix("thz")); // false
//
//        // "that", "the", "them" 都是 "th" 的前缀
//        System.out.println(map.keysWithPrefix("th")); // ["that", "the", "them"]
//
//        // 除了 keysWithPrefix 方法的复杂度取决于返回结果的长度，其他前缀操作的复杂度都是 O(L)，其中 L 是前缀字符串长度。
//        // 你想想上面这几个操作，用 HashMap 或者 TreeMap 能做到吗？应该只能强行遍历所有键，然后一个个比较字符串前缀，复杂度非常高。
//        // 话说，这个 keysWithPrefix 方法，是不是很适合做自动补全功能呢？
//    }
//
//    // 优势三：可以使用通配符
//    public void useWildcards() {
//        // Trie 树的键类型固定为 String 类型，值类型可以是泛型
//        // 支持通配符匹配，"." 可以匹配任意一个字符
//        TrieMap<Integer> map = new TrieMap<>();
//        map.put("that", 1);
//        map.put("the", 2);
//        map.put("team", 3);
//        map.put("zip", 4);
//
//        // 匹配 "t.a." 的键有 "team", "that"
//        System.out.println(map.keysWithPattern("t.a.")); // ["team", "that"]
//
//        // 匹配 ".ip" 的键有 "zip"
//        System.out.println(map.hasKeyWithPattern(".ip")); // true
//
//        // 没有匹配 "z.o" 的键
//        System.out.println(map.hasKeyWithPattern("z.o")); // false
//
//        // 通配符匹配，是不是可以做搜索引擎的关键词匹配呢？这个功能用 HashMap 或者 TreeMap 肯定是做不到的。
//    }
//
//    // 优势四：可以按照字典序遍历键
//    public void dictionaryOrderTraversalKey() {
//        // Trie 树的键类型固定为 String 类型，值类型可以是泛型
//        TrieMap<Integer> map = new TrieMap<>();
//
//        map.put("that", 1);
//        map.put("the", 2);
//        map.put("them", 3);
//        map.put("zip", 4);
//        map.put("apple", 5);
//
//        // 按照字典序遍历键
//        System.out.println(map.keys()); // ["apple", "that", "the", "them", "zip"]
//
//        // 这个功能 TreeMap 也能做到，算是和 Trie 树打了个平手，但是 HashMap 就做不到了。
//        //上面介绍了 Trie 树的特色功能，下面我们来看看它的实现原理。
//    }
//
//    // 【Trie 树的基本结构】
//    // Trie树本质上就是一棵从二叉树衍生出来的多叉树
//    // 二叉树节点的代码实现是这样：
//    // 基本的二叉树节点
//    // class TreeNode {
//    //     int val;
//    //     TreeNode left, right;
//    // }
//    // 其中 left, right 存储左右子节点的指针，所以二叉树的结构是这样：
//
//    // 多叉树节点的代码实现是这样：
//    // 基本的多叉树节点
//    // class TreeNode {
//    //     int val;
//    //     TreeNode[] children;
//    // }
//    // 其中 children 数组中存储指向孩子节点的指针，所以多叉树的结构是这样：
//
//    // 而 TrieMap 中的树节点 TrieNode 的代码实现是这样：
//    // Trie树节点实现
//    static class TrieNode<V> {
//        V val = null;
//        TrieNode<V>[] children = new TrieNode[256];
//        // 这个 val 字段存储键对应的值，children 数组存储指向子节点的指针。
//        // 但是和之前的普通多叉树节点不同，TrieNode 中 children 数组的索引是有意义的，代表键中的一个字符。
//        // 比如说 children[97] 如果非空，说明这里存储了一个字符 'a'，因为 'a' 的 ASCII 码为 97。
//        // 我们的模板只考虑处理 ASCII 字符，所以 children 数组的大小设置为 256。不过这个可以根据具体问题修改。
//        // 比如在实际做题时，题目说了只包含字符 a-z，那么你可以把大小改成 26；或者你不想用字符索引来映射，
//        // 直接用哈希表 HashMap<Character, TrieNode> 也可以，都是一样的效果。
//        // 有了以上铺垫，Trie 树的结构是这样的：
//
//        // 一个节点有 256 个子节点指针，但大多数时候都是空的，可以省略掉不画，所以一般你看到的 Trie 树长这样：
//        // 这是在 TrieMap<Integer> 中插入一些键值对后的样子，白色节点代表 val 字段为空，橙色节点代表 val 字段非空。
//        // 这里要特别注意，TrieNode 节点本身只存储 val 字段，并没有一个字段来存储字符，字符是通过子节点在父节点的 children 数组中的索引确定的。
//        // 形象理解就是，Trie 树用「树枝」存储字符串（键），用「节点」存储字符串（键）对应的数据（值）。所以我在图中把字符标在树枝，键对应的值 val 标在节点上
//    }

//    static class TrieMap<V> {
//        // ASCII码个数
//        private static final int R = 256;
//        // 当前存在Map中的键值对个数
//        private int size                  = 0;
//
//        private static class TrieNode<V> {
//            V val = null;
//            TrieNode<V>[] children = new TrieNode[R];
//        }
//
//        // Trie树的根节点
//        private TrieNode<V> root = null;
//
//        public int size() {
//            return size;
//        }
//
//        // 从节点node开始搜索key，如果存在返回对应节点，否则返回null
//        private TrieNode<V> getNode(TrieNode<V> node, String key) {
//            TrieNode<V> p = node;
//            // 从节点node开始搜索key
//            for (int i = 0; i < key.length(); i++) {
//                if (p == null) {
//                    // 无法向下搜索
//                    return null;
//                }
//                // 向下搜索
//                char c = key.charAt(i);
//                p = p.children[c];
//            }
//            return p;
//        }
//
//        // 有了这个getNode函数，就能实现containsKey方法和get方法了：
//        // 搜索key对应的值，不存在则返回null
//        public V get(String key) {
//            // 从root开始搜索key
//            TrieNode<V> x = getNode(root, key);
//            if (x == null || x.val == null) {
//                // x为空或x的val字段为空都说明key没有对应的值
//                return null;
//            }
//            return x.val;
//        }
//
//        // 判断key是否存在在Map中
//        public boolean containsKey(String key) {
//            return get(key) != null;
//        }
//
//        // 这里需要注意，就算getNode(key)的返回值x非空，也只能说字符串key是一个[前缀]；除非x.val同时非空，才能判断键key存在
//        // 不过，这个特性恰好能够帮我们实现hasKeyWithPrefix方法：
//        // 判断是否存在前缀为prefix的键
//        public boolean hasKeyWithPrefix(String prefix) {
//            // 只要能找到一个节点，就是存在前缀
//            return getNode(root, prefix) != null;
//        }
//
//        // 在所有键中寻找query的最短前缀
//        public String shortestPrefixOf(String query) {
//            TrieNode<V> p = root;
//            // 从节点node开始搜索key
//            for (int i = 0; i < query.length(); i++) {
//                if (p == null) {
//                    // 无法向下搜索
//                    return "";
//                }
//                if (p.val != null) {
//                    // 找到一个键是query的前缀
//                    return query.substring(0, i);
//                }
//                // 向下搜索
//                char c = query.charAt(i);
//                p = p.children[c];
//            }
//            // 这里需要注意的是 for 循环结束之后我们还需要额外检查一下。
//            // 因为之前说了 Trie 树中「树枝」存储字符串，「节点」存储字符串对应的值，
//            // for 循环相当于只遍历了「树枝」，但漏掉了最后一个「节点」，即 query 本身就是 TrieMap 中的一个键的情况。
//            if (p != null && p.val != null) {
//                // 如果query本身就是一个键
//                return query;
//            }
//            return "";
//        }
//
//        // 在所有键中寻找query的最长前缀
//        public String longestPrefixOf(String query) {
//            TrieNode<V> p = root;
//            // 记录前缀的最大长度
//            int max_len = 0;
//
//            // 从节点node开始搜索key
//            for (int i = 0; i < query.length(); i++) {
//                if (p == null) {
//                    // 无法向下搜索
//                    break;
//                }
//                if (p.val != null) {
//                    // 找到一个键是query的前缀，更新前缀的最大长度
//                    max_len = i;
//                }
//                // 向下搜索
//                char c = query.charAt(i);
//                p = p.children[c];
//            }
//            if (p != null && p.val != null) {
//                // 如果query本身就是一个键
//                return query;
//            }
//            return query.substring(0, max_len);
//
//            // 每次遇到 p.val 非空的时候说明找到一个键，但是我们不急着返回，而是更新 max_len 变量，记录最长前缀的长度。
//            // 同样的，在 for 循环结束时还是要特殊判断一下，处理 query 本身就是键的情况。
//        }
//
//        // 接下来，我们来实现 keysWithPrefix 方法，得到所有前缀为 prefix 的键。
//        // 看过前文 手把手刷二叉树（总结篇） 的读者应该可以想到，先利用 getNode 函数在 Trie 树中找到 prefix 对应的节点 x，
//        // 然施展多叉树的遍历算法，遍历以 x 为根的这棵 Trie 树，找到所有键值对
//
//        // 搜索前缀为prefix的所有键
//        public List<String> keyWithPrefix(String prefix) {
//            List<String> res = new LinkedList<>();
//            // 找到匹配prefix在Trie树中那个节点
//            TrieNode<V> x = getNode(root, prefix);
//            if (x == null) {
//                return res;
//            }
//            // DFS遍历以x为根的这棵Trie树
//            traverse(x, new StringBuilder(prefix), res);
//            return res;
//        }
//
//        // 遍历以node节点为根的Trie树，找到所有键
//        private void traverse(TrieNode<V> node, StringBuilder path, List<String> res) {
//            if (node == null) {
//                // 到达Trie树底部叶子节点
//                return;
//            }
//            if (node.val != null) {
//                // 找到一个key，添加到结果列表中
//                res.add(path.toString());
//            }
//            // 回溯算法遍历框架
//            // 我在 关于回溯算法和 DFS 算法的若干问题 中探讨过回溯算法框架和 DFS 算法框架的区别，
//            // 关键在于遍历「节点」和遍历「树枝」的区别。由于 Trie 树将字符存储在「树枝」上，
//            // traverse 函数是在遍历树枝上的字符，所以采用的是回溯算法框架。
//            for (char c = 0; c < R; c++) {
//                // 做选择
//                path.append(c);
//                if (node.children[c] != null) {
//                    traverse(node.children[c], path, res);
//                }
//                // 撤销选择
//                path.deleteCharAt(path.length() - 1);
//            }
//        }
//
//        // 下面来实现 keysWithPattern 方法，使用通配符来匹配多个键，其关键就在于通配符 . 可以匹配所有字符。
//        // 在代码实现上，用 path 变量记录匹配键的路径，遇到通配符时使用类似回溯算法的框架就行了
//        // 通配符.匹配任意字符
//        public List<String> keysWithPattern(String pattern) {
//            List<String> res = new LinkedList<>();
//            traverse(root, new StringBuilder(), pattern, 0, res);
//            return res;
//        }
//
//        // 遍历函数，尝试在[以root为根的Trie树中]匹配pattern[i..]
//        private void traverse(TrieNode<V> node, StringBuilder path, String pattern, int i, List<String> res) {
//            if (node == null) {
//                // 树枝不存在，即字符pattern[i-1]匹配失败
//                return;
//            }
//            if (i == pattern.length()) {
//                // pattern匹配完成
//                if (node.val != null) {
//                    // 如果这个节点存储着val，则找到一个匹配的键
//                    res.add(path.toString());
//                }
//                return;
//            }
//            char c = pattern.charAt(i);
//            if (c == '.') {
//                // pattern[i]是通配符，可以变化成任意字符
//                // 多叉树（回溯算法）遍历框架
//                for (char j = 0; j < R; j++) {
//                    path.append(j);
//                    traverse(node.children[j], path, pattern, i + 1, res);
//                    path.deleteCharAt(path.length() - 1);
//                }
//            } else {
//                // pattern[i]是普通字符c
//                path.append(c);
//                traverse(node.children[c], path, pattern, i + 1, res);
//                path.deleteCharAt(path.length() - 1);
//            }
//            // 可以看到，keysWithPattern 和 keysWithPrefix 的实现是有些类似的，而且这两个函数还有一个潜在的特性：
//            // 它们返回的结果列表一定是符合「字典序」的。
//
//            // 原因应该不难理解，每一个节点的 children 数组都是从左到右进行遍历，即按照 ASCII 码从小到大的顺序递归遍历，得到的结果自然是符合字典序的。
//        }
//
//        // 判断是否存在前缀为prefix的键
//        public boolean hasKeyWithPattern(String pattern) {
//            // 从root节点开始匹配pattern[0..]
//            return hasKeyWithPattern(root, pattern, 0);
//        }
//
//        // 函数定义：从node节点开始匹配pattern[i..]，返回是否成功匹配
//        private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
//            if (node == null) {
//                // 树枝不存在，则匹配失败
//                return false;
//            }
//            if (i == pattern.length()) {
//                // 模式串走到头了，看看匹配到的是否是一个键
//                return node.val != null;
//            }
//            char c = pattern.charAt(i);
//            // 没有遇到通配符
//            if (c != '.') {
//                // 从node.children[c]节点开始匹配pattern[i+1..]
//                return hasKeyWithPattern(node.children[c], pattern, i + 1);
//            }
//            // 遇到通配符
//            for (int j = 0; j < R; j++) {
//                // pattern[i]可以变化成任意字符，尝试所有可能，只要遇到一个匹配成功就返回
//                if (hasKeyWithPattern(node.children[j], pattern, i + 1)) {
//                    return true;
//                }
//            }
//            // 都没有匹配
//            return false;
//        }
//
//        // 在map中添加或修改键值对
//        public void put(String key, V val) {
//            if (!containsKey(key)) {
//                // 新增键值对
//                size++;
//            }
//            // 需要一个额外的辅助函数，并接收其返回值
//            root = put(root, key, val, 0);
//        }
//
//        // 定义：向以node为根的Trie树中插入key[i..]，返回插入完成后的根节点
//        private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
//            if (node == null) {
//                // 如果树枝不存在，新增
//                node = new TrieNode<>();
//            }
//            if (i == key.length()) {
//                // key的路径已插入完成，将值val存入节点
//                node.val = val;
//                return node;
//            }
//            char c = key.charAt(i);
//            // 递归插入子节点，并接收返回值
//            node.children[c] = put(node.children[c], key, val, i + 1);
//            return node;
//            // 因为是递归修改数据结构，所以我们必须额外创建一个返回类型为 TrieNode 的辅助函数，并且在递归调用的时候接收其返回值，拼接到父节点上。
//            // 前文说了，Trie树中的键就是[树枝]，值就是[节点]，所以插入的逻辑就是沿路新建[树枝]，把key的整条[树枝]构建出来之后，在树枝末端的[节点]中存储val
//        }
//
//        // 那么如何控制算法来正确地进行删除呢？
//        // 首先，递归修改数据结构的时候，如果一个节点想删掉自己，直接返回空指针就行了。
//        // 其次，一个节点如何知道自己是否需要被删除呢？主要看自己的 val 字段是否为空以及自己的 children 数组是否全都是空指针。
//
//        // 一个节点要先递归处理子树，然后在后序位置检查自己的 val 字段和 children 列表，判断自己是否需要被删除。
//        // 如果自己的 val 字段为空，说明自己没有存储值，如果同时自己的 children 数组全是空指针，说明自己下面也没有接树枝，即不是任何一个键的前缀。
//        // 这种情况下这个节点就没有存在的意义了，应该删掉自己。
//
//        // 在Map中删除key
//        public void remove(String key){
//            if (!containsKey(key)){
//                return;
//            }
//            // 递归修改数据结构要接收函数的返回值
//            root = remove(root, key, 0);
//            size--;
//        }
//
//        // 定义：在以node为根的Trie树中删除key[i..]，返回删除后的根节点
//        private TrieNode<V> remove(TrieNode<V> node, String key, int i){
//            if (root == null){
//                return null;
//            }
//            if (i == key.length()){
//                // 找到了key对应的TrieNode，删除val
//                node.val = null;
//            }else{
//                char c = key.charAt(i);
//                // 递归去子树进行删除
//                node.children[c] = remove(node.children[c],key, i+1);
//            }
//            // 后序位置，递归路径上的节点可能需要被清理
//            if (node.val != null){
//                // 如果该TrieNode存储着val，不需要被清理
//                return node;
//            }
//            // 检查该TrieNode是否还有后缀
//            for(int c = 0; c < R; c++){
//                if (node.children[c] != null){
//                    // 只要存在一个子节点（后缀树枝），就不需要被清理
//                    return node;
//                }
//            }
//            // 既没有存储val，也没有后缀树枝，则该节点需要被清理
//            return null;
//        }
//    }

    static class TrieMap<V> {
        // ASCII 码个数
        private static final int R = 256;
        // 当前存在 Map 中的键值对个数
        private int size = 0;
        // Trie 树的根节点
        private TrieNode<V> root = null;

        private static class TrieNode<V> {
            V val = null;
            TrieNode<V>[] children = new TrieNode[R];
        }

        // **** 增/改 ****

        // 在 map 中添加或修改键值对
        public void put(String key, V val) {
            if (!containsKey(key)) {
                // 新增键值对
                size++;
            }
            // 需要一个额外的辅助函数，并接收其返回值
            root = put(root, key, val, 0);
        }

        // 定义：向以 node 为根的 Trie 树中插入 key[i..]，返回插入完成后的根节点
        private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
            if (node == null) {

                // 如果树枝不存在，新建
                node = new TrieNode<>();
            }
            if (i == key.length()) {
                // key 的路径已插入完成，将值 val 存入节点
                node.val = val;
                return node;
            }
            char c = key.charAt(i);
            // 递归插入子节点，并接收返回值
            node.children[c] = put(node.children[c], key, val, i + 1);
            return node;
        }

        // **** 删 ****

        // 在 Map 中删除 key
        public void remove(String key) {
            if (!containsKey(key)) {
                return;
            }
            // 递归修改数据结构要接收函数的返回值
            root = remove(root, key, 0);
            size--;
        }

        // 定义：在以 node 为根的 Trie 树中删除 key[i..]，返回删除后的根节点
        private TrieNode<V> remove(TrieNode<V> node, String key, int i) {
            if (node == null) {
                return null;
            }
            if (i == key.length()) {
                // 找到了 key 对应的 TrieNode，删除 val
                node.val = null;
            } else {
                char c = key.charAt(i);
                // 递归去子树进行删除
                node.children[c] = remove(node.children[c], key, i + 1);
            }

            // 后序位置，递归路径上的节点可能需要被清理
            if (node.val != null) {
                // 如果该 TireNode 存储着 val，不需要被清理
                return node;
            }
            // 检查该 TrieNode 是否还有后缀
            for (int c = 0; c < R; c++) {
                if (node.children[c] != null) {
                    // 只要存在一个子节点（后缀树枝），就不需要被清理
                    return node;
                }
            }
            // 既没有存储 val，也没有后缀树枝，则该节点需要被清理
            return null;
        }

        // **** 查 ****

        // 搜索 key 对应的值，不存在则返回 null
        public V get(String key) {
            // 从 root 开始搜索 key
            TrieNode<V> x = getNode(root, key);
            if (x == null || x.val == null) {
                // x 为空或 x 的 val 字段为空都说明 key 没有对应的值
                return null;
            }
            return x.val;
        }

        // 判断 key 是否存在在 Map 中
        public boolean containsKey(String key) {
            return get(key) != null;
        }

        // 判断是和否存在前缀为 prefix 的键
        public boolean hasKeyWithPrefix(String prefix) {
            // 只要能找到一个节点，就是存在前缀
            return getNode(root, prefix) != null;
        }

        // 在所有键中寻找 query 的最短前缀
        public String shortestPrefixOf(String query) {
            TrieNode<V> p = root;
            // 从节点 node 开始搜索 key
            for (int i = 0; i < query.length(); i++) {
                if (p == null) {
                    // 无法向下搜索
                    return "";
                }
                if (p.val != null) {
                    // 找到一个键是 query 的前缀
                    return query.substring(0, i);
                }
                // 向下搜索
                char c = query.charAt(i);
                p = p.children[c];
            }

            if (p != null && p.val != null) {
                // 如果 query 本身就是一个键
                return query;
            }
            return "";
        }

        // 在所有键中寻找 query 的最长前缀
        public String longestPrefixOf(String query) {
            TrieNode<V> p = root;
            // 记录前缀的最大长度
            int max_len = 0;

            // 从节点 node 开始搜索 key
            for (int i = 0; i < query.length(); i++) {
                if (p == null) {
                    // 无法向下搜索
                    break;
                }
                if (p.val != null) {
                    // 找到一个键是 query 的前缀，更新前缀的最大长度
                    max_len = i;
                }
                // 向下搜索
                char c = query.charAt(i);
                p = p.children[c];
            }

            if (p != null && p.val != null) {
                // 如果 query 本身就是一个键
                return query;
            }
            return query.substring(0, max_len);
        }

        // 搜索前缀为 prefix 的所有键
        public List<String> keysWithPrefix(String prefix) {
            List<String> res = new LinkedList<>();
            // 找到匹配 prefix 在 Trie 树中的那个节点
            TrieNode<V> x = getNode(root, prefix);

            if (x == null) {
                return res;
            }
            // DFS 遍历以 x 为根的这棵 Trie 树
            traverse(x, new StringBuilder(prefix), res);
            return res;
        }

        // 遍历以 node 节点为根的 Trie 树，找到所有键
        private void traverse(TrieNode<V> node, StringBuilder path, List<String> res) {
            if (node == null) {
                // 到达 Trie 树底部叶子结点
                return;
            }

            if (node.val != null) {
                // 找到一个 key，添加到结果列表中
                res.add(path.toString());
            }

            // 回溯算法遍历框架
            for (char c = 0; c < R; c++) {
                // 做选择
                path.append(c);
                traverse(node.children[c], path, res);
                // 撤销选择
                path.deleteCharAt(path.length() - 1);
            }
        }

        // 通配符 . 匹配任意字符
        public List<String> keysWithPattern(String pattern) {
            List<String> res = new LinkedList<>();
            traverse(root, new StringBuilder(), pattern, 0, res);
            return res;
        }

        // 遍历函数，尝试在「以 node 为根的 Trie 树中」匹配 pattern[i..]
        private void traverse(TrieNode<V> node, StringBuilder path, String pattern, int i, List<String> res) {
            if (node == null) {
                // 树枝不存在，即匹配失败
                return;
            }
            if (i == pattern.length()) {
                // pattern 匹配完成
                if (node.val != null) {
                    // 如果这个节点存储着 val，则找到一个匹配的键
                    res.add(path.toString());
                }
                return;
            }
            char c = pattern.charAt(i);

            if (c == '.') {
                // pattern[i] 是通配符，可以变化成任意字符
                // 多叉树（回溯算法）遍历框架
                for (char j = 0; j < R; j++) {
                    path.append(j);
                    traverse(node.children[j], path, pattern, i + 1, res);
                    path.deleteCharAt(path.length() - 1);
                }
            } else {
                // pattern[i] 是普通字符 c
                path.append(c);
                traverse(node.children[c], path, pattern, i + 1, res);
                path.deleteCharAt(path.length() - 1);
            }
        }

        // 判断是和否存在前缀为 prefix 的键
        public boolean hasKeyWithPattern(String pattern) {
            // 从 root 节点开始匹配 pattern[0..]
            return hasKeyWithPattern(root, pattern, 0);
        }

        // 函数定义：从 node 节点开始匹配 pattern[i..]，返回是否成功匹配
        private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
            if (node == null) {
                // 树枝不存在，即匹配失败
                return false;
            }
            if (i == pattern.length()) {
                // 模式串走到头了，看看匹配到的是否是一个键
                return node.val != null;
            }
            char c = pattern.charAt(i);
            // 没有遇到通配符
            if (c != '.') {
                // 从 node.children[c] 节点开始匹配 pattern[i+1..]
                return hasKeyWithPattern(node.children[c], pattern, i + 1);
            }
            // 遇到通配符
            for (int j = 0; j < R; j++) {
                // pattern[i] 可以变化成任意字符，尝试所有可能，只要遇到一个匹配成功就返回
                if (hasKeyWithPattern(node.children[j], pattern, i + 1)) {
                    return true;
                }
            }
            // 都没有匹配
            return false;
        }

        // 从节点 node 开始搜索 key，如果存在返回对应节点，否则返回 null
        private TrieNode<V> getNode(TrieNode<V> node, String key) {

            TrieNode<V> p = node;
            // 从节点 node 开始搜索 key
            for (int i = 0; i < key.length(); i++) {
                if (p == null) {
                    // 无法向下搜索
                    return null;
                }
                // 向下搜索
                char c = key.charAt(i);
                p = p.children[c];
            }
            return p;
        }

        public int size() {
            return size;
        }
    }

    static class TrieSet {
        // 底层用一个 TrieMap，键就是 TrieSet，值仅仅起到占位的作用
        // 值的类型可以随便设置，我参考 Java 标准库设置成 Object
        private final TrieMap<Object> map = new TrieMap<>();

        // **** 增 ****

        // 在集合中添加元素 key
        public void add(String key) {
            map.put(key, new Object());
        }

        // **** 删 ****

        // 从集合中删除元素 key
        public void remove(String key) {
            map.remove(key);
        }

        // **** 查 ****

        // 判断元素 key 是否存在集合中
        public boolean contains(String key) {
            return map.containsKey(key);
        }

        // 在集合中寻找 query 的最短前缀
        public String shortestPrefixOf(String query) {
            return map.shortestPrefixOf(query);
        }

        // 在集合中寻找 query 的最长前缀
        public String longestPrefixOf(String query) {
            return map.longestPrefixOf(query);
        }

        // 在集合中搜索前缀为 prefix 的所有元素
        public List<String> keysWithPrefix(String prefix) {
            return map.keysWithPrefix(prefix);
        }

        // 判断集合中是否存在前缀为 prefix 的元素
        public boolean hasKeyWithPrefix(String prefix) {
            return map.hasKeyWithPrefix(prefix);
        }

        // 通配符 . 匹配任意字符，返回集合中匹配 pattern 的所有元素
        public List<String> keysWithPattern(String pattern) {
            return map.keysWithPattern(pattern);
        }

        // 通配符 . 匹配任意字符，判断集合中是否存在匹配 pattern 的元素
        public boolean hasKeyWithPattern(String pattern) {
            return map.hasKeyWithPattern(pattern);
        }

        // 返回集合中元素的个数
        public int size() {
            return map.size();
        }
    }
}
